//
<<<<<<< HEAD:cxx/algorithm/src/permutation.cc
// Created by liushuai on 2020/4/29.
//
#include "permutation.h"
void permutation(string&s,vector<string>&result,int start){
    if(start == s.length()-1)
        result.push_back(s);
    else{
        for(int i=start;i<s.length();i++){
            swap(s.at(start),s.at(i));
            permutation(s,result,start+1);
            swap(s.at(start),s.at(i));
        }
    }
}
vector<string> permutation(string& s){
    vector<string> result;
    if(s.empty())
        return result;
    else{
        permutation(s,result,0);
    }
    return result;
}

=======
// Created by liushuai on 2020/4/8.
//
#include "permutation.h"
void permutation(std::vector<std::string>& result, std::string s, int begin) {
  int s_size = s.size();
  if (begin == s_size - 1) result.push_back(s);
  for (int i = begin; i < s_size; i++) {
    swap(s.at(i), s.at(begin));
    permutation(result, s, begin + 1);
    swap(s.at(i), s.at(begin));
  }
}
vector<string> permutation(string s) {
  vector<string> result;
  if (s.size() == 0)
    return result;
  else {
    permutation(result, s, 0);
    return result;
  }
}

std::vector<std::vector<int>> permuteDFS(std::vector<int>& nums) {
  std::vector<std::vector<int>> result;
  const int n = nums.size();
  std::vector<std::pair<int, std::vector<int>>> node_stack;
  node_stack.push_back(std::pair<int, std::vector<int>>(0, nums));
  std::vector<int> temp;

  while (!node_stack.empty()) {
    auto top = node_stack.back();
    node_stack.pop_back();

    temp = top.second;
    if (top.first == n - 1) {
      result.push_back(top.second);
    }
    int start = top.first;
    while (start < n) {
      if (start == top.first)
        node_stack.push_back(
            std::pair<int, std::vector<int>>(top.first + 1, temp));
      else {
        std::swap(temp[top.first], temp[start]);
        node_stack.push_back(
            std::pair<int, std::vector<int>>(top.first + 1, temp));
        std::swap(temp[top.first], temp[start]);
      }
      start++;
    }
  }
  return result;
}

void permute(vector<int>& nums, vector<vector<int>>& cache, int start) {
  if (start == nums.size()) {
    cache.push_back(nums);
  } else {
    for (int i = start; i < nums.size(); i++) {
      std::swap(nums[start], nums[i]);
      permute(nums, cache, start + 1);
      std::swap(nums[start], nums[i]);
    }
  }
}
vector<vector<int>> permute(vector<int>& nums) {
  vector<vector<int>> res;
  if (nums.empty())
    return res;
  else
    permute(nums, res, 0);
  return res;
}
>>>>>>> dev:cxx/algorithm/common/src/permutation.cc
